#include<iostream>
#include<queue>
#include<vector>
using namespace std;

class Solution {
public:
    int dx[4] = { 0, 0, 1, -1 };
    int dy[4] = { 1, -1, 0, 0 };
    int m, n;
    queue<pair<int, int>> qu;

    void _bfs(vector<vector<int>>& grid, int x, int y)
    {
        for (int k = 0; k < 4; k++) {
            int xx = x + dx[k];
            int yy = y + dy[k];
            if (xx >= 0 && xx < m && yy >= 0 && yy < n && grid[xx][yy] == 1) {
                grid[xx][yy] = 2;
                qu.push(make_pair(xx, yy));
            }
        }
    }

    int orangesRotting(vector<vector<int>>& grid) {
        m = grid.size();
        n = grid[0].size();
        int digit = 0;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] > 0) digit++;
                if (grid[i][j] == 2) qu.push(make_pair(i, j));
            }
        }
        if (digit == 0) return 0;
        int time = -1;
        int level = qu.size();
        while (!qu.empty()) {
            for (int lev = 0; lev < level; lev++) {
                _bfs(grid, qu.front().first, qu.front().second);
                qu.pop();
            }
            level = qu.size();
            time++;
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) return -1;
            }
        }
        return time;
    }
};